package com.huangyi;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //在每个数行中找最大值
        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode() {}
            TreeNode(int val) { this.val = val; }
            TreeNode(int val, TreeNode left, TreeNode right) {
                    this.val = val;
                    this.left = left;
                    this.right = right;
            }
        }
        class Solution {
            public List<Integer> largestValues(TreeNode root) {
                List<Integer> result = new ArrayList<>();
                if (root == null) return result;

                Queue<TreeNode> q = new ArrayDeque<>();
                q.offer(root);

                while (!q.isEmpty()) {
                    int size = q.size();                  // 本层节点数（固定次数）
                    int max = Integer.MIN_VALUE;          // 本层最大值初始化为整型最小

                    for (int i = 0; i < size; i++) {
                        TreeNode cur = q.poll();          // 弹出本层一个节点
                        max = Math.max(max, cur.val);     // 维护本层最大值

                        if (cur.left != null) q.offer(cur.left);
                        if (cur.right != null) q.offer(cur.right);
                    }
                    result.add(max);                       // 收录本层答案
                }
                return result;
            }
        }


        //最后一块石头的重量
    }
}